package org.example.Greedy_Algorithm;

import java.util.ArrayList;
import java.util.Arrays;

public class Jumping_game {
    public static void main(String[] args) {
        //跳跃游戏

        //给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
        //判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
        int[] nums = {1,0,1,0};
        boolean b = canJump(nums);
        System.out.println(b);
    }

    //自己思考，自己编写，没有任何借鉴达到最优，这是学习算法以来的一大进步
    public static boolean canJump(int[] nums) {
        if (nums.length<=1) return true;
        ArrayList<Integer> indice = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                indice.add(i);
            }
        }
        boolean flag = true;
        for (int i = 0; i < indice.size(); i++) {
            if (!flag) break;
            int step = 1;
            flag = false;
            for (int j = indice.get(i)-1; j >= 0; j--) {
                if (indice.get(indice.size()-1)== nums.length-1 && i==indice.size()-1){
                    if (nums[j] >= step){
                        flag = true;
                        break;
                    }
                }else {
                    if (nums[j] > step){
                        flag = true;
                        break;
                    }
                }
                step++;
            }
        }
        return flag;
    }
}
